package 剑指offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;

/**
 * 
 * @author ：soulstones
 * @version ：2019年9月30日 下午9:49:43 @Description：
 * 
 *          数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，
 *          因此输出2。如果不存在则输出0。
 */
public class A28数组当中出现次数超过一半的数字 {

	// 数组当中的数字超过了一半
	// 直接找到中位数就是了\

	// 基于快排思想
	public static int MoreThanHalfNum_Solution(int[] array) {
		if (array.length <= 0)
			return Integer.MIN_VALUE;
		int start = 0, length = array.length - 1, end = length - 1;
		int mid = length >> 1; // 右移，相当于除以2
		int index = Partition(array, start, end);
		while (index != mid) {
			if (index > mid) {
				index = Partition(array, start, end);
			} else {
				index = Partition(array, start, end);
			}
		}
		int result = array[mid];
		int times = 0;
		for (int i = 0; i < length; ++i) {
			if (array[i] == result)
				times++;
		}
		if (times * 2 < length) {
			System.out.println(times);
			return 0;
		} else {
			return result;
		}
	}

	public static int Partition(int[] arr, int start, int end) {
		int flag = (arr[start] + arr[end]) / 2;

		while (start < end) {
			while (arr[end] > flag) {
				end--;
			}
			swap(arr, start, end);
			while (arr[start] <= flag) {
				start++;
			}
			swap(arr, start, end);

		}
		return start;
	}

	public static void swap(int[] array, int num1, int num2) {
		int temp = array[num1];
		array[num1] = array[num2];
		array[num2] = temp;
	}

	
	
	//方法2,基于HashMap
	public static int MoreThanHalfNum_Solution1(int[] array) {

		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

		for (int i = 0; i < array.length; i++) {

			if (!map.containsKey(array[i])) {
				map.put(array[i], 1);
			} else {
				int count = map.get(array[i]);
				map.put(array[i], ++count);
			}
		}
		Iterator iter = map.entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			Integer key = (Integer) entry.getKey();
			Integer val = (Integer) entry.getValue();
			if (val > array.length / 2) {
				return key;
			}
		}
		return 0;
	}

	
	//时间复杂度O（n）
	//利用超过一半的信息，进行巧解
	

		  public static int MoreThanHalfNum_Solution3(int [] array) {
		        Arrays.sort(array);
		        int count=0;
		         
		        for(int i=0;i<array.length;i++){
		            if(array[i]==array[array.length/2]){
		                count++;
		            }
		        }
		        if(count>array.length/2){
		            return array[array.length/2];
		        }else{
		            return 0;
		        }
		         
		    }
	
	/*
 6
2 3 4 3 3 3
3
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int size = scanner.nextInt();
		int [] arr=new int [size];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=scanner.nextInt();
		}
		int res = MoreThanHalfNum_Solution1(arr);
		System.out.println(res);
	}

}
